package com.learn;

import java.util.Arrays;

public class insertionSort {
    public static void insertionSort(int[] array) {
        int len = array.length;
        if (len <= 1) {
            return;
        }

        for (int i = 1; i < len; i++) {
            //取出未排序的当前要参与排序的元素
            int current = array[i];
            //在已排序数组中定义一个前置索引，从后向前扫描
            int preIndex = i - 1;
            //从后向前依次和当前元素作比较
            while (preIndex >= 0 && array[preIndex] > current) {
                //比较时元素大于当前元素，则将元素向后移动一位
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            //元素<当前元素，则将当前元素插入到它后面
            array[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] array = {2, 1, 7, 3,2, 9, 5};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }
}
